D - Knapsack 1

1次元で考えると、作るDPテーブルは

i番目までの荷物の中から選んだ時の、価値の総和の最大値

遷移をする時に必要な条件は何か

というのを考えた時に、このままでは遷移が上手くいきません。なぜなら

5番目までの荷物の中から、10kg入る鞄に入れた時、価値の最大は4500円だった。

6番目まで入れた時の最大値は？

という風になった時に、もしかすると4500円時点で満タンかもしれないし、実は指輪だけ入れててスカスカかもしれない。

今の鞄の状態を把握するには、価値の総和だけでなく、あとどれだけ入るか？という情報が必要。なので状態を付け足す。

というのが多次元DPのお気持ちの1つだそうだ。（知らんけど）

それを元に遷移を考えてみると

5番目までの荷物の中から、10kg入る鞄に入れた時、価値の最大は

・残り9kg入る状態で3000円

・残り4kg入る状態で3500円

・残り1kg入る状態で4500円

なんだけどどうする？

みたいな感じになる。よく分からん。